import java.util.Random;

class Solution1 {
    public void swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

    public void sortColors(int[] nums) {
        int len = nums.length;
        int left = -1, right = len, i = 0;
        while (i < right) {
            if (nums[i] == 1) {
                i++;
            } else if (nums[i] == 0) {
                swap(nums, ++left, i);
            } else {
                swap(nums, --right, i);
            }
        }
    }
}

class Solution2 {
    public void swap(int[] nums,int a,int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

    public void qSort(int[] nums, int begin, int end) {
        if (begin >= end) return;

        int key = nums[new Random().nextInt(end - begin+1)+begin];
        int left = begin - 1, right = end+1, i = begin;

        while(i<right) {
            if(nums[i]<key) swap(nums,++left,i++);
            else if(nums[i] == key) i++;
            else swap(nums,--right,i);
        }

        qSort(nums, begin, key - 1);
        qSort(nums, key + 1, end);
    }

    public int[] sortArray(int[] nums) {
        qSort(nums, 0, nums.length - 1);
        return nums;
    }
}

class Solution {
    public class ListNode {
      int val;
      ListNode next;
      ListNode(int x) { val = x; }
  }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur =l1;
        StringBuffer str1 = new StringBuffer();
        StringBuffer str2 = new StringBuffer();
        while(cur!=null) {
            str1.append(cur.val);
            cur = cur.next;
        }
        cur = l2;
        while(cur!=null) {
            str2.append(cur.val);
            cur = cur.next;
        }
        str1.reverse();
        str2.reverse();
        int n1 = Integer.valueOf(str1.toString());
        int n2 = Integer.valueOf(str2.toString());
        int n3 = n1+n2;
        String str3 = String.valueOf(n3);
        ListNode l3 = new ListNode(0);
        for(int i = 0; i < str3.length(); i++) {
            ListNode node = new ListNode(str3.charAt(i)-'0');
            node.next = l3.next;
            l3.next = node;
        }
        return l3.next;
    }
}

public class Test {
}
